package Other;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

public class drabStack {
    /*解决单调栈问题 - 给你一个数组 ,要求 你求每一个数的左边的最大值 / 最小值 和 右边的最大值/最小值*/
    public static ArrayList<int[]> getMaxStack(int[] arr){
        //第一种没有重复值的情况,且 求左右俩边的最大值
        if (arr == null)return null;
        ArrayList<int[]> result = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();//维护栈的结构从大到小
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]){
                int[] cur = new int[3];
                cur[0] = arr[stack.pop()];//代表这个数
               if (!stack.isEmpty())cur[1] = arr[stack.peek()];//代表这个数左边离他最近的最大值
                cur[2] = arr[i];//代表右边这个数离他最近的最大值
                result.add(cur);//存入到结果集中
            }
            stack.push(i);//将大的数压入进去
        }
        while (!stack.isEmpty()){//处理数组走完,但是栈不为空的情况
            int[] cur = new int[3];
            cur[0] = arr[stack.pop()];
            if (!stack.isEmpty())cur[1] = arr[stack.peek()];
            result.add(cur);
        }
        //这里面用 0 代表没有最大值
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {5,4,3,6,1,2};
        getMaxStack(arr);
    }
}
